#include <stdio.h>
#include <stdlib.h>
#include "Array.h"


struct array {
	ElemType*   heap;
	int         length;
	int         size;
};


// Initiate an array. O(1)
int ArrayInit(Array* arr) {
	arr->heap = (ElemType*) malloc(ARRAY_INIT_SIZE * sizeof(ElemType));
	// Memery is full.
	if (arr->heap == NULL) {
		return 1;
	}
	arr->length = 0;
	arr->size = ARRAY_INIT_SIZE;
	return 0;
}


// Grow array's size. O(1)
int ArrayGrow(Array* arr) {
	ElemType* rtn = (ElemType*)
	realloc(arr->heap, (arr->size + ARRAY_INCREMENT) * sizeof(ElemType));
	if (rtn == NULL) {
		return 1;
	}
	arr->heap = rtn;
	arr->size += ARRAY_INCREMENT;
	// printf("Note: Array size grow to %d\n", arr->size);
	return 0;
}


// Append element to the end of the array. O(1)
int ArrayAppend(Array* arr, ElemType elem) {
	if (arr->length >= arr->size) {
		ArrayGrow(arr);
	}
	arr->heap[arr->length] = elem;
	arr->length += 1;
	return 0;
}


// Print an array seperate by space. O(length)
int ArrayPrint(Array* arr) {
	for (int idx = 0; idx < arr->length; idx += 1) {
		printf("%d ", arr->heap[idx]);
	}
	printf("\n");
	return 0;
}


// Clear an array. O(1)
int ArrayClear(Array* arr) {
	arr->length = 0;
	return 0;
}


// Insert elem to arr[idx].
int ArrayInsert(Array* arr, int idx, ElemType elem) {
	if (arr->length >= arr->size) {
		ArrayGrow(arr);
	}
	for (int i = arr->length - 1; i >= idx; i -= 1) {
		arr->heap[i+1] = arr->heap[i];
	}
	arr->heap[idx] = elem;
	arr->length += 1;
	return 0;
}


// Return the length of array.
int ArrayLength(Array* arr) {
	return arr->length;
}


// Return 1 means array is empty.
int ArrayIsEmpty(Array* arr) {
	return arr->length <= 0;
}


// Pop arr[idx] and return its value.
ElemType ArrayPop(Array* arr, int idx) {
	ElemType target = arr->heap[idx];
	for (int i = idx; i < arr->length - 1; i += 1) {
		arr->heap[i] = arr->heap[i+1];
	}
	arr->length -= 1;
	return target;
}


// Return elem's index in array.
int ArrayIndex(Array* arr, ElemType elem) {
	for (int idx = 0; idx < arr->length; idx += 1) {
		if (arr->heap[idx] == elem) {
			return idx;
		}
	}
	return -1;
}


// Destroy an array, free the memory in heap.
int ArrayDestroy(Array* arr) {
	free(arr->heap);
	arr->heap = NULL;
	arr->length = 0;
	arr->size = 0;
    return 0;
}


int main() {
	Array arr;
	ArrayInit(&arr);
	for (int x = 1; x <= 200; x += 1) {
		ArrayAppend(&arr, x);
	}
	ArrayPrint(&arr);
	ArrayClear(&arr);
	for (int x = 1; x <= 10; x += 1) {
		ArrayAppend(&arr, x);
	}
	ArrayPrint(&arr);
	ArrayClear(&arr);
	for (int x = 1; x <= 100; x += 1) {
		ArrayInsert(&arr, 0, x);
	}
	ArrayPrint(&arr);
	for (int x = 0; x < 10; x += 1) {
		printf("Pop element: %d\n", ArrayPop(&arr, 0));
	}
	ArrayPrint(&arr);
	printf("%d\n", ArrayIndex(&arr, 10));
	ArrayDestroy(&arr);
	return 0;
}
